<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>快速排序</title>
  </head>

  <body>
    <h5>快速排序</h5>
    <p>
      快速排序也叫分区排序，从数组中随机选择一个元素作为基准，小于元素的移到基准左边，大于元素的移到基准右边；递归调用直至子集只剩下一个元素
    </p>
    <script>
      function quickSort(arr) {
        if (arr.length <= 1) {
          return arr
        }
        var tempIndex = Math.floor(arr.length / 2)
        var tempVal = arr.splice(tempIndex, 1)[0] // 每次循环少遍历一次
        var left = [],
          right = []
        for (let i = 0; i < arr.length; i++) {
          if (arr[i] < tempVal) {
            left.push(arr[i])
          } else {
            right.push(arr[i])
          }
        }
        return quickSort(left).concat(tempVal, quickSort(right))
      }
      console.log(quickSort([5, 1, 4, 2, 3, 8]))
    </script>
  </body>
</html>
